/*
 * @Author: szx
 * @Date: 2021-11-22 13:52:19
 * @LastEditTime: 2022-03-18 13:51:48
 * @Description:
 * @FilePath: \leetcode\1-99\79\79.js
 */
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    const m = board.length;
    const n = board[0].length;
    const flag = Array.from(new Array(m), () => {
        return new Array(n).fill(false);
    });
    const dfs = function (i, j, index) {
        if (index == word.length) return true;
        if (i < 0 || i >= m || j < 0 || j >= n || flag[i][j]) {
            return false;
        }
        if (word[index] == board[i][j] && !flag[i][j]) {
            flag[i][j] = true;
            if (dfs(i + 1, j, index + 1)) return true;
            if (dfs(i, j + 1, index + 1)) return true;
            if (dfs(i - 1, j, index + 1)) return true;
            if (dfs(i, j - 1, index + 1)) return true;
        }
        flag[i][j] = false;
        return false;
    };
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] == word[0]) {
                if (dfs(i, j, 0)) return true;
            }
        }
    }
    return false;
};
console.log(
    exist(
        [
            ['C', 'A', 'A'],
            ['A', 'A', 'A'],
            ['B', 'C', 'D']
        ],
        'CAC'
    )
);
